420C - Bug in Code - CodeForces Solution


data structures graphs implementation two pointers *1900

Please click on ads to support us..

C++ Code:

#include<iostream>
#include  <algorithm>
struct programmer
{
	long long y;
	long long x;
};
programmer p[300000];
long long vote[300000];
long long rp[300000];
long long py[300000];
long long result;
long long n;
long long m;
long long j;
bool predicate(programmer a, programmer b)
{
	if (a.x != b.x)
	{
		return a.x < b.x;
	}
	else
	{
		return a.y < b.y;
	}
}
int main()
{
	std::cin >> n >> m;
for (long long i = 1; i <= n; i++)
{
	std::cin >> p[i].x >> p[i].y;
	vote[p[i].x]++;
	vote[p[i].y]++;
	rp[p[i].x]++;
	rp[p[i].y]++;
	if (p[i].x > p[i].y)
		std::swap(p[i].y, p[i].x);
}
		std::sort(p + 1, p + 1 + n, predicate);
std::sort(rp + 1, rp + 1 + n);
long long start = 1;
for (long long i = 1; i <= n; i++)
{
	long long t = 0;
	long long vertex = 0;
	
	for (j = start; j <= n; j++)
    {
if (p[j].x != i)
{
	if (t != 0)
	{
		if (vote[i] + vote[vertex] - t < m && vote[i] + vote[vertex] >= m)
		{
			result -= 2;
		}
	}
	break;
}
if (j == start)
{
	vertex = p[j].y;
	t++;
}
else
{
	if (p[j].y == vertex)
	{
		t++;
	}
	else
	{
		if (vote[i] + vote[vertex] - t < m && vote[i] + vote[vertex] >= m)
		{
			result -= 2;
		}
		t = 1;
		vertex = p[j].y;
	}
}
    }
	if (j == n + 1)
{
	if (t != 0)
	{
		if (vote[i] + vote[vertex] - t < m && vote[i] + vote[vertex] >= m)
		{
			result -= 2;
		}
	}
}
start = j;
long long left=1;
long long right=n;
long long check =m - vote[i];
if (vote[i] * 2 >= m)
{
	result--;
}

while (left < right)
{
	long long mid = (left + right) / 2;
	if (rp[mid] < check)
	{
		left = mid + 1;
	}
	else
	{
		right = mid;
	}
}
if (rp[right] < check)
	right++;
result += n - right + 1;

}
std::cout << result / 2 << '\n';
    return 0;
}/*1698160193.2336645*/


Comments

Submit
0 Comments
More Questions

107B - Basketball Team
245A - System Administrator
698A - Vacations
1216B - Shooting
368B - Sereja and Suffixes
1665C - Tree Infection
1665D - GCD Guess
29A - Spit Problem
1097B - Petr and a Combination Lock
92A - Chips
1665B - Array Cloning Technique
1665A - GCD vs LCM
118D - Caesar's Legions
1598A - Computer Game
1605A - AM Deviation
1461A - String Generation
1585B - Array Eversion
1661C - Water the Trees
1459A - Red-Blue Shuffle
1661B - Getting Zero
1661A - Array Balancing
1649B - Game of Ball Passing
572A - Arrays
1455A - Strange Functions
1566B - MIN-MEX Cut
678C - Joty and Chocolate
1352E - Special Elements
1520E - Arranging The Sheep
1157E - Minimum Array
1661D - Progressions Covering